/*
 * Question: Try to travel a postfix order threaded
 * binary tree from the first node to the last,
 * vice versa.
 *
 * Date: 01/27/2012
 */

#include <iostream>
#include "iofile.h"
#include "bthtree.h"
using namespace std;

class bthtree : public _bthtree<bthtree, char>{};

void visit(bthtree *rt)
{
    cout << rt->key << " ";
}

void postorder_pred(bthtree *rt)
{
    bthtree *p;

    p = rt;
    while (p){
        visit(p);
        if (p->rtag == BTT_LINK)
            p = p->rchild;
        else if (p->ltag == BTT_LINK)
            p = p->lchild;
        else
            p = p->lchild;
    }
}

void postorder_succ(bthtree *rt)
{
    bthtree *p;

    if (!rt) return;
    p = rt;
    while (p->ltag == BTT_LINK || p->rtag == BTT_LINK){
        if (p->ltag == BTT_THREAD)
            p = p->rchild;
        else
            p = p->lchild;
    }
    while (p){
        visit(p);
        if (p == rt)
            p = NULL;
        else if (p == p->parent->rchild)
            p = p->parent;
        else{
            p = p->parent;
            if (p->rchild){
                p = p->rchild;
                while (p->ltag == BTT_LINK || p->rtag == BTT_LINK){
                    if (p->ltag == BTT_THREAD)
                        p = p->rchild;
                    else
                        p = p->lchild;
                }
            }
        }
    }
}

int main()
{
    bthtree *rt;

    open_input("chap06/misc02.txt");
    bthtree_postcreate<bthtree, char>(rt);
    postorder_succ(rt);
    cout << endl;
    postorder_pred(rt);
    cout << endl;
    bthtree_destory(rt);
    close_input();
    return 0;
}
